package _01_动态数组;

public class _74_搜索二维矩阵 {

    public static void main(String[] args) {
        _74_搜索二维矩阵 v = new _74_搜索二维矩阵();
        int[][] ins = new int[][]{
                {1}
        };
        System.out.println(v.searchMatrix(ins, 2));

    }

    public boolean searchMatrix(int[][] matrix, int target) {
        int rows = matrix.length - 1;
        int cols = matrix[0].length - 1;
        int leftRow = 0;
        int leftCol = 0;
        int rightRow = rows;
        int rightCol = cols;
        while (leftRow <= rightRow && leftCol <= rightCol) {
            // 取中位数
            int midRow = leftRow + rightRow >> 1; //
            int midCol = leftCol + rightCol >> 1;
            if (target == matrix[midRow][midCol]) {
                return true;
            } else if (target < matrix[midRow][midCol]) {
                if (midCol > 0) {
                    rightCol = midCol - 1;
                } else {
                    rightRow = midRow - 1;
                    rightCol = cols;
                }
            } else {
                if (midCol < cols) {
                    leftCol = midCol + 1;
                } else {
                    leftRow = midRow + 1;
                    leftCol = 0;
                }
            }
        }
        return false;
    }

}
